import java.util.HashSet;

public class Test {
    /**
     * 滑动窗口算法，解决连续子数组问题
     * */
    public int lengthOfLongestSubstring1(String s) {
//无重复子数组最长连续字符
        //写法一,数组模拟哈希表
        char[] chars = s.toCharArray();//转为字符数组
        int len=0,n=chars.length;
        int[] hash=new int[128];//使用ascll码值进行统计数组内部每个位置的数量，128即可够了
        for(int left=0,right=0;right<n;right++){
            hash[chars[right]]++;//进窗口
            while(hash[chars[right]]>1){//判断
                hash[chars[left++]]--;
            }
            len=Math.max(len,right-left+1);//更新结果
        }
        return len;
    }
    public int lengthOfLongestSubstring2(String s) {

        //写法二，直接使用哈希表
        HashSet<Character> set = new HashSet<Character>();
        int len=0,n=s.length();
        int left=0;
        for(int right=0;right<n;right++){
            char ch=s.charAt(right);
            while(set.contains(ch)){
                set.remove(s.charAt(left++));
            }
            set.add(ch);
            len=Math.max(len,right-left+1);//更新结果
        }
        return len;
    }

    public int longestOnes(int[] nums, int k) {
        int zero=0;
        int n=nums.length;
        int len=0;
        for(int left=0,right=0;right<n;right++){
            if(nums[right]==0){//进窗口
                zero++;
            }
            while(zero>k){//判断
                if(nums[left++]==0)zero--;//出窗口
            }
            len=Math.max(len,right-left+1);//更新结果
        }
        return len;
    }
    public static void main(String[] args) {
        String s="abcabcbb";

        System.out.println("方法一(模拟哈希表):"+new Test().lengthOfLongestSubstring1(s));
        System.out.println("方法二(使用哈希表):"+new Test().lengthOfLongestSubstring2(s));
        System.out.println("=================");
        int[] nums={1,1,1,0,0,0,1,1,1,1,0};
        System.out.println("最大连续1的个数:"+new Test().longestOnes(nums, 2));

    }
}
